package com.da.javatest.niuke.jianzhi;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.da.javatest.niuke.common.TreeNode;

/**
 * @author chenlida
 * @date 2020/10/21 19:44
 * https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?
 * tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C22Solution {
    private List<List<Integer>> datas = new ArrayList<>();

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        search(root, 1);
        ArrayList<Integer> result = new ArrayList<>();
        for (List<Integer> data : datas) {
            result.addAll(data);
        }
        return result;
    }

    // 二叉树前序遍历
    private void search(TreeNode root, int level) {
        if (root != null) {
            if (datas.size() < level) {
                datas.add(new ArrayList<>());
            }
            datas.get(level - 1).add(root.val);
            search(root.left, level + 1);
            search(root.right, level + 1);
        }
    }

    public ArrayList<Integer> PrintFromTopToBottom2(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> ChildNode = new LinkedList<>();
        result.add(root.val);
        if (root.left != null) {
            ChildNode.offer(root.left);
        }
        if (root.right != null) {
            ChildNode.offer(root.right);
        }
        while (ChildNode.size() != 0) {
            root = ChildNode.poll();
            result.add(root.val);
            if (root.left != null) {
                ChildNode.offer(root.left);
            }
            if (root.right != null) {
                ChildNode.offer(root.right);
            }
        }
        return result;
    }
}
